package com.leetcode.LeetCode精选TOP面试题;

/**
 * @author 覃国强
 * @date 2022-07-17 13:52
 */
public class 题库_0240_搜索二维矩阵II {

  static
  class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {

      int si = 0;
      int sj = 0;
      int ei = matrix.length - 1;
      int ej = matrix[0].length - 1;

      while (si <= ei && sj <= ej) {

        if (si == ei || sj == ej) {
          return searchInOneRowOrColumn(matrix, si == ei, si, sj, ej, target);
        }

        int mi = (si + ei) / 2;
        int mj = (sj + ej) / 2;

        int rowNum = matrix[mi][sj];
        int columnNum = matrix[si][mj];

        // 判断行
        if (rowNum == target) {
          return true;
        } else if (rowNum < target) {
          si = mi;
        } else {
          ei = mi;
        }


        // 判断列
        if (columnNum == target) {
          return true;
        } else if (columnNum < target) {
          sj = mj;
        } else {
          ej = mj;
        }
      }
      return false;
    }

    public boolean searchInOneRowOrColumn(int[][] matrix, boolean isRow, int index, int s, int e, int target) {
      while (s <= e) {
        int m = (s + e) / 2;
        int num = isRow ? matrix[index][m] : matrix[m][index];
        if (num == target) {
          return true;
        }
        if (num < target) {
          s = m + 1;
        } else {
          e = m - 1;
        }
      }
      return false;
    }


  }

}
